Presupunem ca avem N elemente disticte. Acestea sunt impartite in m muntlimi:

ex N=10, m=3
A={1,3,8} B={2,4,5,9} C={6,7,10} 

Este necesar sa facem reuniunea a X multimi (voi explica cazul clasicii reuniuni a 2 multimi):

Vom stoca elemente asfel incat sa ne dam seama carei multimi apartine un el. la primul pas in O(1).

poz  1 \2 \3 \4 \5 \6 \7 \8 \9 \10 
el   1 \2 \1 \2 \2 \6 \6 \1 \2 \6 

Dupa cum se obesrva initial le-am stocat dupa primul element aparut in sir , in acest caz minimul.

Algritmul initial simplist in O(N^2) este:

void merge(x,y) // fuzioneaza multumile etichetate cu x, y
{
	int i=x,j=y;
	if (i>j)
		swap(i,j);
	for (int k=j;k<N;++k)
		if (a[k]==j)
			a[k]=i;
} 

Ca sa optimizam cautarea unui element , restectiv fuziunarea intre multimi ne vom gandi la multimi ca la niste arbori.
Nodul tata va fi in "eticheta" multimii. Pentru ca operatii le sa se realizeze optim vom tranforma arborele (multimea) 
cu H mai mica in cea cu inaltime mai mare.
Fuziunea se va face asa , dupa modificand algoritmul de cautare in arbore/multime:

// H- inaltimea , set- vectorul multimilor

void merge(int a, int b)
{
	if (H[a]==H[b])
	{
		++H[a];
		set[b]=a;
	}
	else
		if (H[a]>H[b])
			set[b]=a;
		else
			set[a]=b;
}

Cel mai eficient algoritm de gasire a drumului este urmatorul , neputand fi mai comprimat de atat.

int find(int x) // return -> "eticheta" multimii care il contine pe x
{
	int r=x; // r e radacina arborelui
	while (set[r]!=r)
		r=set[r];
	int i=x;
	while (i!=r)
	{
		j=set[i];
		set[i]=r;
		i=j;
	}
	return r;
}

Ideea de baza a algoritmului find este aceea de a comprima drumul. Intai se gasete tatal nodului x. Apoi se marcheaza pe drumul spre acest nod niste scurtaturi pentru 
toate valorile din set[].
